package _543cloud_new;

import java.io.IOException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class Max_match {

	private Set<Match> matchs = new HashSet<Match>();
	private Set<Match> path = new HashSet<Match>();
	private Graph simplegraph = new Graph();

	public Max_match(String s1, String s2) throws IOException {
		this.simplegraph = new Graph(s1, s2){};
	}

	public void printMatchInfo() {
		System.out.println(matchs);
	}

	public int findMatch() {
		Iterator<Left_node> iterl = simplegraph.lnode_queue.iterator();
		while (iterl.hasNext()) {
			Left_node temp_l = iterl.next();
			if (hasAugmentPath(temp_l)) {
				for (Match match : path) {
					if (matchs.contains(match)) 
						matchs.remove(match);
					else 
						matchs.add(match);	
				}
			}
			path.clear();
		}
		return matchs.size();
	}

	private boolean hasAugmentPath(Left_node lnode) {
		Iterator<Right_node> temp = lnode.l_r.iterator();
		while(temp.hasNext()){
			Right_node temp_r =temp.next();

			Match match = new Match(lnode.name, temp_r.name);
			if (matchs.contains(match)) {
				if (lnode.l_r.size() == 1) 
					return false;
			} 
			else {
				path.add(match);
				if (!temp_r.isUsed()) {
					temp_r.setUsed(true);
					return true;
				} 
				else {
					for (Left_node c : temp_r.r_l) {
						Match m = new Match(c.name, temp_r.name);
						if (path.contains(m)) {
							if (temp_r.r_l.size() == 1) 
								return false;
						} 
						else if (matchs.contains(m)) {
							path.add(m);
							if (hasAugmentPath(c)) 
								return true;
							 else
								path.remove(m);
						} 
					}
					path.remove(match);
				}
			}
		
		}
		return false;
	}

	public static void main(String[] args) throws IOException {

		Max_match test = new Max_match("src/_543cloud_new/capacity.txt",
				"src/_543cloud_new/relation.txt");
		System.out.println("Maximum Bipartitie-Graph match is ["
				+ test.findMatch() + "]");
		test.printMatchInfo();
	}

}
